package algorithm.dynamic;

/**
 * leetcode : https://leetcode.com/problems/unique-paths/description/
 * Difficulty : Medium
 *
 * 给一个 长宽 分别为 m 和 n 的方块矩阵。一个小人从左上角走到右下角，问有多少条不同的路径
 *
 * 思路：动态规划
 * 要走到[m,n] 有两种方式：
 * 1）从[(m-1),n] 走
 * 2）从[m,(n-1)] 走
 *
 * 那么有递推公式：
 * pathNum(m,n) = pathNum(m-1,n) + pathNum(m, n-1)
 *
 * 在最上面一行和最左边一列，pathNum都为1。因为只有一条路到达，不能往回走
 *
 * @Author Antony
 * @Since 2018/7/18 17:56
 */
public class UniquePaths {

    public static void main(String[] args) {
        int m=3;
        int n=7;
        System.out.println(uniquePaths(m,n));
    }

    /**
     * beats 100.0% - 0ms
     * 时间复杂度，空间复杂度 都为 O(M*N)
     */
    public static int uniquePaths(int m, int n) {
        if(m==0 || n==0) return 0;
        if(m==1 || n==1) return 1;
        int[][] grid = new int[m][n];
        int tmp;
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(i==0 || j==0){
                    tmp = 1;
                }else{
                    tmp = grid[i-1][j] + grid[i][j-1];
                }
                grid[i][j] = tmp;
            }
        }
        return grid[m-1][n-1];
    }
}
